#include <iostream>
#include <bitset>

#include <time.h>

int main() {
    const int N = 2000000;

    clock_t start = clock();

    std::bitset<N+1> bitSet;

    // 假设大于等于2的都是素数
    bitSet.flip();
    bitSet.reset(0);
    bitSet.reset(1);

    for (int i = 2; i * i <= N; i++) {
        // 如果i是素数
        if (bitSet.test(i)) {
            // i*(i+...)的都是合数
            for (int j = i * i; j <= N; j += i) {
                bitSet.reset(j);
            }
        }
    }

    clock_t end = clock();
    double millis = 1000.0 * (end - start) / CLOCKS_PER_SEC;

    using std::cout;
    cout << bitSet.count() << " primes\n" << millis << " milliseconds\n";
}

// g++ -O3 ch09/sieve/Sieve.cpp && ./a && rm ./a